FIG. 1A shows a wireless communication system 1 in which a receiver 2, labelled RX wishes to receive data from each of k user terminals 10 (henceforth referred to as terminals), labelled TX1, TX2, . . . , TXk, in its field of view 3 (there could also be multiple receivers and multiple corresponding fields of view). Communications takes place over a medium 5 which must be shared among all the terminals. The terminals may be stationary (at a fixed location), or they may be mobile e.g. portable, or fitted to a vehicle, aircraft or vessel, or space vehicle, or carried by a person or animal). We are interested in the case where there is no feedback channel from the receiver to the transmitters.
The absence of a feedback channel may be desirable to reduce the implementation complexity, cost, or power consumption of a terminal, since the terminal does not need to provide communications receiver functionality. This is of particular importance in situations, such as field deployable sensors, where terminals may be battery powered, or have a limited power source. Systems with no feedback channel from the receiver to the terminals will be called “open-loop”.
There are several examples of systems which fit this model. These are described for illustrative purposes only, and are not intended to restrict the application of the described methods.
One example is a low earth orbit satellite communications, where the field of view is the footprint of the satellite, and the transmitters are ground based sensor devices equipped with wireless transmitters for the purposes of transmitting sensor data to the satellite. In this example, the field of view moves over the surface of the earth as the satellite orbits. From an orbital altitude of 700 km, the field of view is of the order of 6000 km wide. FIG. 1B shows an example of a communication system with a satellite receiver with a moving field of view for communicating with k transmitters. At a first point in time the receiver has a first field of view 6 which contains transmitters TX1, and TX2. At a later time, the satellite has moved to the right, and thus has a new field of view 7 which contains transmitters TXi, TXj and TXk. In one scenario, power consumption is critical for both the ground based sensors and the satellite payload. In order to increase the lifetime of the sensors and to reduce the cost of the payload it may be advantageous to have no feedback link from the satellite to the sensors.
Another example is cellular communications, where the field of view is the coverage area (sometimes called a cell) of a particular base station. Again, the terminals may be low cost sensors equipped with cellular transmitters in order to send their sensor data to the base station but lacking a feedback channel to allow coordination of transmissions as is typically performed in cellular communications systems.
The shared physical communications medium may be partitioned into a number of channels. These channels may be time slots in a time division multiple access system, frequency slots in a frequency division multiple access system, subcarriers in an orthogonal frequency division multiple access system, or spreading sequences in a code division multiple access system. More generally, the slots may be hybrids of any of these, where a slot corresponds to some subset of the overall degrees of freedom of the system (including degrees of freedom resulting from the use of multiple transmit and or receive antennas). Regardless of the underlying method of dividing the medium into channels, we shall refer to these channels as “slots”. We do not require that the slots be orthogonal, although in many instances slots are chosen to be orthogonal.
In some embodiments the receiver is equipped with a multiuser decoder that is capable of successfully decoding some number of simultaneous transmissions by different terminals within the same slot. In practice, the number of simultaneous transmissions within a slot that can be successfully decoded depends on a variety of systems parameters, including the received signal to noise ratio, the radio channel propagation characteristics between each terminal and the receiver, and the kind of multiuser decoder being used. For the sake of a simple explanation, we will assume that the multiuser receiver can successfully decode m≧1 simultaneous transmissions within a single slot. More detailed receiver characteristics can be easily taken into account if they are known.
However in such systems a problem exists in determining how to allocate terminals to slots in order to maximise system performance. There are several metrics of system performance that could be adopted. We are interested in improving the probability that the receiver can correctly decode the data transmitted by the terminals. In other words, we would like to minimise the probability that the number of simultaneous transmissions exceeds m in a given slot, where m is the receiver characteristic described above (ie the maximum number of transmissions in a slot that the receiver can successfully decode).
The allocation of terminals to slots is made more difficult by the lack of a feedback channel from the receiver. This prevents the use of coordinated slot allocation in which the allocation is performed by some central controller. There are a number of known approaches to this problem such as fixed allocation, and random access.
A fixed allocation method permanently allocates one slot to each terminal. This is an instance of circuit switching where the slot is allocated for the entire duration of system operation. This approach has several well-known disadvantages. It is wasteful of channel resources, as it does not allow slots to be re-used. Furthermore, the slot allocations must be hard-wired into the terminals when the system is open-loop, as there is no other way to control the channel allocation after deployment. In a system where the terminals are mobile (or where the field of view itself moves, for example in a low-earth-orbit satellite system), it may not be known in advance which terminals will be in the field of view. As a result, fixed allocation can assign only up to m terminals to any one slot. In a satellite communications context, this slot would not be able to be reused by any other terminals globally.
Another well-known approach to slot allocation is random access (also known as slotted ALOHA). In this approach, slots are assigned to terminals randomly. Suppose that we have k terminals in the field of view and n available slots. Under the random access approach, each terminal selects a slot uniformly at random. Then the probability that a particular slot is chosen by m terminals is
                              P          m                =                              (                                                            k                                                                              m                                                      )                    ⁢                                    (                                                                    1                                                                                        n                                                              )                        m                    ⁢                                    (                                                                                          n                      -                      1                                                                                                            n                                                              )                                      k              -              m                                                          Equation        ⁢                                  ⁢        1            
This is known to be well approximated by the Poisson approximation to the binomial distribution:
                                          P            m                    ≈                                    1                              m                !                                      ⁢                          e                              -                λ                                      ⁢                          λ              m                        ⁢                                                  ⁢            where            ⁢                                                  ⁢            λ                          =                  k          n                                    Equation        ⁢                                  ⁢        2            
Using this approximation, the probability that a slot has more than m terminals is 1−Q(m+1, λ) where
                              Q          ⁡                      (                          a              ,              z                        )                          =                                            Γ              ⁡                              (                                  a                  ,                  z                                )                                                    Γ              ⁡                              (                a                )                                              =                                    1                                                (                                      a                    -                    1                                    )                                !                                      ⁢                                          ∫                z                ∞                            ⁢                                                t                                      a                    -                    1                                                  ⁢                                  e                                      -                    t                                                  ⁢                d                ⁢                                                                  ⁢                t                                                                        Equation        ⁢                                  ⁢        3            is the regularised incomplete gamma function. FIG. 2 plots curves 20 of the probability that a slot has more than m terminals versus λ=k/n for m=1, 2, . . . , 10. Given a particular target decoder failure probability p, which is the probability that a slot contains more than m terminals, we can compute the maximum value of λ=k/n that is supported for this random access scheme as:λ(p)=Q−1(m+1,1−p)  Equation 4where Q−1 is the inverse regularised gamma function (which can be easily numerically computed using software such as Mathematica). Curves 30 of the maximal values of λ(p) versus m for p=10−1, 10−2, . . . , 10−6 are plotted in FIG. 3. From this figure, we see that if we desire a very low probability of decoder failure, we are restricted to a low value of λ=k/n. For example at p=10−6 and m=5, we can only support k≈n/3 terminals in n slots, despite being able to decode 5 simultaneous users in a slot. If we are willing to accept a higher probability of decoder failure, then we can support many more terminals. For example, at p=0.1 and m=5, we can support k=3n terminals. However in cases where there is no feedback channel, a higher probability is typically less desirable, as there is no way to request retransmission of failed transmissions.
There is thus a need to provide methods and systems for determining how to allocate terminals to slots in order to improve, and if possible, maximise system performance compared to such fixed and random access allocation schemes, or alternatively to at least provide users with a useful alternative to such schemes.